package org.example.struct.array2;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author liyishan
 * @date 2024/7/31 09:17
 * @apiNote
 */

public class Test03111MinRectanglesToCoverPoints {
    public static void main(String[] args) {
        int[][] points = new int[][]{{0,0},{1,1},{2,2},{3,3},{4,4},{5,5},{6,6}};
        int w = 2;
        int res = minRectanglesToCoverPoints(points, w);
        System.out.println(res);
    }

    public static int minRectanglesToCoverPoints(int[][] points, int w) {
        Arrays.sort(points, Comparator.comparingInt(a -> a[0]));
        int count = 0;
        int left = points[0][0];
        if(points.length ==  1){
            return 1;
        }
        for (int i = 1; i < points.length; i++) {
            if(i == points.length - 1){
                count++;
            }
            if(left + w < points[i][0]) {
                count++;
                left = points[i][0];
            }
        }
        return count;
    }

    public int minRectanglesToCoverPointsPlus(int[][] points, int w) {
        Arrays.sort(points, Comparator.comparingInt(a -> a[0]));
        int count = 1;
        int left = points[0][0];
        for (int i = 1; i < points.length; i++) {
            if(left + w < points[i][0]) {
                count++;
                left = points[i][0];
            }
        }
        return count;
    }

    public int minRectanglesToCoverPoints1(int[][] points, int w) {
        Arrays.sort(points, Comparator.comparingInt(a -> a[0]));
        int count = 0;
        int left = -1;
        for(int[] p:points){
            if(p[0] > left){
                left = p[0]+w;
                count++;
            }
        }
        return count;
    }

}
